{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "总结了一两种常用的线程模型，归纳了进程间通信与线程同步的最佳实践，以期用简单规范的方式开发功能正确、线程安全的多线程程序。\n",
    "\n",
    "文中的\"多线程服务器\"是指运行在 Linux操作系统上的独占式网络应用程序。不考虑做分布式存储，只考虑分布式计算，系统的规模大约是几十台服务器到几百台服务器之间。\n",
    "\n",
    "\"服务器\"这个词有时指程序，有时指进程，有时指硬件（无论虚拟的或直实的）。请注意按上下文区分。另外，本书不考虑虚拟化的场景，当我说\"两个进程不在同一台机器上\"时，指的是逻辑上不在同-个操作系统里运行，虽然物理上可能位于同一机器虚拟出来的两台\"虚拟机\"上。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 3.1 进程与线程\n",
    "\n",
    "**\"进程(process )\"**是操作里最重要的两个概念之一（另一个是文件），粗略地讲，一个进程是\"内存中正在运行的程序\"。\n",
    "\n",
    "本书的进程指的是 Linux 操作系统通过`fork()`系统调用产生的那个东西，或者Windows下`CreateProcess()`的产物，不是Erlang 里的那种\"轻量级进程（Actor）\"。\n",
    "\n",
    "每个进程有自己独立的地址空间（address space），\"在同一个进程\"还是\"不在同一个进程\"是系统功能划分的重要决策点。《Erlang 程序设计》【ERL】把\"进程\"比喻为\"人\"，我觉得十分精当，为我们提供了一个思考的框架。\n",
    "\n",
    "每个人有自己的记忆（memory）.人与人通过谈话（消息传递）来交流，谈话既可以是面谈（同一台服务器），也可以在电话里谈（不同的服务器，有网络通信）。面谈和电话谈的区别在于，面谈可以立即知道对方是否死了（crash，SIGCHLD），而电话谈只能通过周期性的心跳来判断对方是否还活着。\n",
    "\n",
    "有了这些比喻，设计分布式系统时可以采取\"角色扮演\"，团队里的几个人各自扮演一个进程，人的角色由进程的代码决定（管登录的、管消息分发的、管买卖的等等）。每个人有自己的记忆，但不知道别人的记忆，要想知道别人的看法，只能通过交谈（暂不考虑共享内存这种IPC）。\n",
    "\n",
    "然后就可以思考:\n",
    "- 容错: 万一有人突然死了\n",
    "- 扩容: 新人中途加进来\n",
    "- 负载均衡: 把甲的活儿挪给乙做\n",
    "- 退休: 甲要修复 bug，先别派新任务，等他做完手上的事情就把他重启\n",
    "\n",
    "等等各种场景，十分便利。\n",
    "\n",
    "**\"线程\"**这个概念大概是在1993年以后才慢慢流行起来的，距今不到 20年，比不得有40年光辉历史的Unix 操作系统。线程的出现给Unix添了不少乱，很多C库函数（`strtok()`、`ctime()`）不是线程安全的，需要重新定义（§4.2）; signal的语意也大为复杂化。据我所知，最早支持多线程编程的（民用）操作系统是 Solaris 2.2和Windows NT3.1，它们均发布于1993年。随后在1995年，POSIX threads标准确立。\n",
    "\n",
    "线程的特点是共享地址空间，从而可以高效地共享数据。一台机器上的多个进程能高效地共享代码段（操作系统可以映射为同样的物理内存），但不能共享数据。如果多个进程大量共享内存，等于是把多进程程序当成多线程来写，掩耳盗铃。\n",
    "\n",
    "\"多线程\"的价值，我认为是为了更好地发挥多核处理器（multi-cores）的效能在单核时代，多线程没有多大价值。Alan Cox说过∶\"A computer is a state machine. Threads are for people who can't program state machines.\"（计算机是一台状态机。线程是给那些不能编写状态机程序的人准备的。）如果只有一块CPU、一个执行单元，那么确实如 Alan Cox 所说，按状态机的思路去写程序是最高效的，这正好也是下一节展示的编程模型。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 3.2 线程服务器的常用编程模型\n",
    "\n",
    "[UNP]对此有很好的总结（第6章的IO模型、第30章的客户端/服务器设计范式），这里不再赘述。\n",
    "\n",
    "据我了解，在高性能的网络程序中，使用得最为广泛的恐怕要数\"non-blocking IO + IO multiplexing\"这种模型，即Reactor模式，我知道的有\n",
    "> - http://www.cs.wustl.edu/~schmidt/PDF/Reactor1-93.pdf\n",
    "> - http://www.cs.wustl.edu/~schmidt/PDF/Reactor2-93.pdf\n",
    "- lighttpd，单线程服务器。（Nginx与之类似，每个工作进程有一个eventloop。）\n",
    "- libevent, libev。\n",
    "- ACE, Poco C++ libraries。\n",
    "- Java NIO，包括 Apache Mina 和 Netty。\n",
    "- POE (Perl)。\n",
    "- Twisted (Python)。\n",
    "\n",
    "相反，Boost.Asio 和Windows I/O Completion Ports实现了Proactor模式，应用面似乎要窄一些。此外，ACE也实现了[Proactor模式](https://www.cs.wm.edu/~dcschmidt/PDF/Reactor.pdf)。\n",
    "\n",
    "在\"non-blocking IO + IO multiplexing\"这种模型中，程序的基本结构是一个事件循环(event loop)，以事件驱动(event-driven)和事件回调的方式实现业务逻辑∶"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "vscode": {
     "languageId": "cpp"
    }
   },
   "outputs": [],
   "source": [
    "// 代码仅为示意，没有完整考虑各种情况\n",
    "\n",
    "while(!done) {\n",
    "  int timeout_ms = max(1000, getNextTimedCallback());\n",
    "  int retval = ::poll(fds, nfds, timeout_ms);\n",
    "  if (retval <0) {\n",
    "\t// 处理错误，回调用户的 error handler\n",
    "  } \n",
    "  else {\n",
    "\t// 处理到期的 timers，回调用户的 timer handler\n",
    "\tif(retval > 0) { \n",
    "    \t// 处理 IO 事件，回调用户的 IO event handler\n",
    "    }\n",
    "  }\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "这里`select(2)/poll(2)`有伸缩性方面的不足，Linux下可替换为`epoll(4)`，其他操作系统也有对应的[高性能替代品](http://www.kegel.com/c10k.html)。\n",
    "\n",
    "Reactor模型的优点很明显，编程不难，效率也不错。不仅可以用于读写socket，连接的建立(`connect(2)/accept(2)`)甚至DNS解析都可以用非阻塞方式进行，以提高并发度和吞吐量（throughput），对于IO密集的应用是个不错的选择。lighttpd就是这样，它内部的`fdevent`结构十分精妙，值得学习\n",
    "> `gethostbyname(3)`是阻塞的，对陌生域名解析的耗时可长达数秒\n",
    "\n",
    "基于事件驱动的编程模型也有其本质的缺点，它要求事件回调函数必须是非阻塞的。对于涉及网络 IO的请求响应式协议，它容易割裂业务逻辑，使其散布于多个回调函数之中，相对不容易理解和维护。现代的语言有一些应对方法（例如`coroutine`），但是本书只关注C++这种传统语言，因此就不展开讨论了。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 3.3 多线程服务器的常用编程模型\n",
    "\n",
    "> - https://blog.csdn.net/Solstice/article/details/5307710\n",
    "> - http://files.cppblog.com/Solstice/multithreaded_server.pdf\n",
    "\n",
    "这方面我能找到的文献不多，大概有这么几种（见§6.6更详细的讨论）:\n",
    "> - http://www.cs.uwaterloo.ca/~brecht/pubs.html\n",
    "> - http://hal.inria.fr/docs/00/67/44/75/PDF/paper.pdf\n",
    "\n",
    "1. 每个请求创建一个线程，使用阻塞式IO操作。在Java1.4引入NIO之前，这是Java 网络编程的推荐做法。可惜伸缩性不佳。\n",
    "2. 使用线程池，同样使用阻塞式IO操作。与第1种相比，这是提高性能的措施。\n",
    "3. 使用 `non-blocking IO + IOmultiplexing`。即 Java NIO 的方式。\n",
    "4. `Leader/Follower`等高级模式。\n",
    "\n",
    "\n",
    "在默认情况下，我会使用第3种，即`non-blocking IO + one loop per thread`模式来编写多线程C++网络服务程序。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 3.3.1 one loop per thread\n",
    "\n",
    "此种模型下，程序里的每个IO线程有一个event loop（或者叫Reactor），用于处理读写和定时事件（无论周期性的还是单次的），代码框架跟S3.2一样。\n",
    "\n",
    "libev 的作者说:\n",
    "- One loop per thread is usually a good model. Doing this is almost never wrong, sometimes a better-performance model exists, but it is always a good start.\n",
    "\n",
    "这种方式的好处是∶\n",
    "- 线程数目基本固定，可以在程序启动的时候设置，不会频繁创建与销毁。\n",
    "- 可以很方便地在线程间调配负载。\n",
    "- IO事件发生的线程是固定的，同一个TCP连接不必考虑事件并发。\n",
    "\n",
    "`Event loop` 代表了线程的主循环，需要让哪个线程干活，就把 `timer`或`IO channel`（如TCP 连接）注册到哪个线程的loop里即可。对实时性有要求的`connection` 可以单独用一个线程; 数据量大的`connection` 可以独占一个线程，并把数据处理任务分摊到另几个计算线程中（用线程池）; 其他次要的辅助性 `connections` 可以共享一个线程。\n",
    "\n",
    "对于non-trivial的服务端程序，一般会采用`non-blocking IO ＋ IO multiplexing`，每个`connection/acceptor`都会注册到某个`event loop` 上，程序里有多个`event loop`，每个线程至多有一个`event loop`。\n",
    "\n",
    "多线程程序对 `event loop`提出了更高的要求，那就是\"线程安全\"。要允许一个线程往别的线程的loop 里塞东西，这个loop 必须得是线程安全的。如何实现一个优质的多线程 Reactor? 可参考第8章。\n",
    "> 比方说主IO线程收到一个新建连接，分配给某个子IO线程处理"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 3.3.2 线程池\n",
    "\n",
    "不过，对于没有IO而光有计算任务的线程，使用`event loop`有点浪费，我会用一种补充方案，即用blocking queue实现的任务队列（TaskQueue）:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "vscode": {
     "languageId": "cpp"
    }
   },
   "outputs": [],
   "source": [
    "typedef boost::function<void()> Functor;\n",
    "BlockingQueue<Functor> taskQueue; // 线程安全的阻塞队列"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "用这种方式实现线程池特别容易，以下是启动容量（并发数）为`N`的线程池∶"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "vscode": {
     "languageId": "cpp"
    }
   },
   "outputs": [],
   "source": [
    "void workerThread()\n",
    "{\n",
    "\twhile(running) // running 变量是个全局标志\n",
    "    {\n",
    "\t\tFunctor task = taskQueue.take(); // this blocks \n",
    "        task(); //在产品代码中需要考虑异常处理\n",
    "    }\n",
    "}\n",
    "\n",
    "int N = num_of_computing_threads;\n",
    "for(int i = 0; i < N; ++ti)\n",
    "{\n",
    "    create_thread(&workerThread); // 伪代码∶启动线程\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "使用起来也很简单∶"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "vscode": {
     "languageId": "cpp"
    }
   },
   "outputs": [],
   "source": [
    "Foo foo; // Foo 有 calc()成员函数\n",
    "boost::function<void()> task = boost::bind(&Foo::calc, &foo);\n",
    "taskQueue.post(task);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "上面十几行代码就实现了一个简单的固定数目的线程池，功能大概相当于Java中的 `ThreadPoolExecutor` 的某种\"配置\"。当然，在真实的项目中，这些代码都应该封装到一个class中，而不是使用全局对象。另外需要注意一点∶`Foo` 对象的生命期，第1章详细讨论了这个问题。\n",
    "\n",
    "muduo 的[线程池](../../muduo/muduo/base/ThreadPool.h)比这个略复杂，因为要提供`stop()`操作。\n",
    "\n",
    "除了任务队列，还可以用`BlockingQueue<T>`实现数据的生产者消费者队列，即`T`是数据类型而非函数对象，`queue`的消费者(s)从中拿到数据进行处理。\n",
    "> 数据类型如`std::string`或`google::protobuf::Message*`。\n",
    "\n",
    "`BlockingQueue<T>`是多线程编程的利器，它的实现可参照Java util.concurrent里的（ArraylLinked）BlockingQueue。这份 Java 代码可读性很高，代码的基本结构和教科书一致（1个mutex，2个condition variables），健壮性要高得多。如果不想自己实现，用现成的库更好。muduo 里有一个基本的实现，包括无界的`BlockingQueue`和有界的`BoundedBlockingQueue`两个class。有兴趣的读者还可以试试 Intel ThreadingBuilding Blocks里的 `concurrent_queue<T>`，性能估计会更好。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 3.3.3 推荐模式\n",
    "\n",
    "总结起来，我推荐的C++多线程服务端编程模式为∶`one(event) loop per thread + thread pool`。\n",
    "\n",
    "- event loop（也叫 IO loop）用作IO multiplexing，配合non-blocking IO和定时器。\n",
    "- thread pool用来做计算，具体可以是任务队列或生产者消费者队列。\n",
    "\n",
    "以这种方式写服务器程序，需要一个优质的基于 Reactor 模式的网络库来支撑，muduo 正是这样的网络库。\n",
    "\n",
    "程序里具体用几个loop、线程池的大小等参数需要根据应用来设定，基本的原则是\"阻抗匹配\"，使得 CPU和IO 都能高效地运作，具体的例子见 p.80。\n",
    "\n",
    "此外，程序里或许还有个别执行特殊任务的线程，比如 `logging`，这对应用程序来说基本是不可见的，但是在分配资源（CPU 和IO）的时候要算进去，以免高估了系统的容量。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 3.4 进程间通信只用TCP\n",
    "\n",
    "Linux下进程间通信(IPC)的方式数不胜数，光[UNPv2]列出的就有∶匿名管道（pipe）、具名管道（FIFO）、POSIX消息队列、共享内存、信号（signals）等等，更不必说 Sockets了。\n",
    "\n",
    "同步原语（synchronization primitives）也很多、如互斥器（mutex）、条件变量（condition variable）、读写锁（reader-writer lock）、文件锁（record locking）、信号量（semaphore）等等。\n",
    "\n",
    "如何选择呢? 根据我的个人经验，贵精不贵多，认真挑选三四样东西就能完全满足我的工作需要，而且每样我都能用得很熟，不容易犯错。\n",
    "\n",
    "进程间通信我首选 Sockets（主要指TCP，我没有用过 UDP，也不考虑 Unix domain 协议），其最大的好处在于∶可以跨主机，具有伸缩性。反正都是多进程了，如果一台机器的处理能力不够，很自然地就能用多台机器来处理。把进程分散到同一局域网的多台机器上，程序改改`host:port`配置就能继续用。相反，前面列出的其他IPC都不能跨机器 ，这就限制了`scalability`。\n",
    "> 比如共享内存效率最高，但受网络带宽及延迟限制，无论如何也不能高效地共享两台物理机器的内存。\n",
    "\n",
    "在编程上，TCP sockets 和 pipe 都是操作文件描述符，用来收发字节流，都可以`read/write/fcntl/select/poll`等。不同的是，TCP是双向的，Linux的pipe是单向的，进程间双向通信还得开两个文件描述符，不方便(可以用`socketpair(2)`替代。); 而且进程要有父子关系才能用 pipe，这些都限制了pipe 的使用。在收发字节流这一通信模型下，没有比 Sockets/TCP更自然的IPC了。当然，pipe也有一个经典应用场景，那就是写`Reactor/event loop` 时用来异步唤醒 `select`（或等价的 `poll/epoll_wait`）调用(在Linux下，可以用`eventfd(2)`代替，效率更高)，[Sun HotSpot JVM](https://blog.csdn.net/haoel/article/details/2224055)在 Linux就是这么做的。\n",
    "\n",
    "TCP port 由一个进程独占，且操作系统会自动回收（listening port和已建立连接的 TCP socket 都是文件描述符，在进程结束时操作系统会关闭所有文件描述符）。这说明，即使程序意外退出，也不会给系统留下垃圾，程序重启之后能比较容易地恢复，而不需要重启操作系统（用跨进程的mutex 就有这个风险）。还有一个好处，既然 port是独占的，那么可以防止程序重复启动，后面那个进程抢不到 port，自然就没法初始化了，避免造成意料之外的结果。\n",
    "\n",
    "两个进程通过 TCP通信，如果一个崩溃了，操作系统会关闭连接，另一个进程几乎立刻就能感知，可以快速 failover。当然应用层的心跳也是必不可少的（S9.3）。\n",
    "\n",
    "与其他 IPC 相比，TCP 协议的一个天生的好处是\"可记录、可重现\"。`tcpdump`和`Wireshark`是解决两个进程间协议和状态争端的好帮手，也是性能（吞吐量、延迟）分析的利器。我们可以借此编写分布式程序的自动化回归测试。也可以用`tcpcopy`之类的工具进行压力测试。TCP还能跨语言，服务端和客户端不必使用同一种语言。试想如果用共享内存作为IPC，C++程序如何与 Java 通信，难道用JNI吗?\n",
    "\n",
    "另外，如果网络库带\"连接重试\"功能的话，我们可以不要求系统里的进程以特定的顺序启动，任何一个进程都能单独重启。换句话说，TCP连接是可再生的，连接的任何一方都可以退出再启动，重建连接之后就能继续工作、这对开发牢靠的分布式系统意义重大。\n",
    "\n",
    "使用TCP这种字节流（byte stream）方式通信，会有`marshal/unmarshal`的开销，这要求我们选用合适的消息格式，准确地说是 wirte format，目前我推荐Google Protocol Buffers。见§9.6关于分布式系统消息格式的讨论。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> AI:\n",
    "\n",
    "在使用 TCP 进行通信时，数据在传输过程中会以字节流（byte stream）的形式进行传输。而在数据传输的两端，则需要将数据从原本的数据结构序列化（marshal）为字节流的形式，以便传输；在接收端，还需要将接收到的字节流反序列化（unmarshal）为原本的数据结构。这些序列化和反序列化的过程就会产生一定的开销，因为需要将数据结构转化为字节流，并将字节流转化为对应的数据结构。这种开销对于数据量较大的情况下会更加明显"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "有人或许会说，具体问题具体分析，如果两个进程在同一台机器，就用共享内存，否则就用TCP. 比如 MS SQL Server 就同时支持这两种通信方式。试问，是否值得为那么一点性能提升而让代码的复杂度大大增加呢? 何况 TCP的local吞吐量一点都不低，见§6.5.1的测试结果。TCP是字节流协议，只能顺序读取，有写缓冲; 共享内存是消息协议，a进程填好一块内存让b进程来读，基本是\"停等（stop wait）\"方式。要把这两种方式揉到一个程序里需要建一个抽象层，封装两种IPC。这会带来不透明性，并且增加测试的复杂度。而且万一通信的某一方崩溃，状态 reconcile 也会比 sockets 麻烦。（数据刚写到一半，怎么办?）为我所不取。再说了，你舍得让几万块买来的 SQL. Server 和其他应用程序分享机器资源吗?生产环境下的数据库服务器往往是独立的高配置服务器，一般不会同时运行其他占资源的程序。\n",
    "\n",
    "TCP本身是个数据流协议，除了直接使用它来通信外，还可以在此之上构建RPC/HTTP/SOAP之类的上层通信协议，这超过了本章的范围。另外，除了点对点的通信之外，应用级的广播协议也是非常有用的，可以方便地构建可观可控的分布式系统，见§7.11。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 分布式系统中使用TCP长连接通信\n",
    "\n",
    "§3.1提到，分布式系统的软件设计和功能划分一般应该以\"进程\"为单位。从宏观上看，一个分布式系统是由运行在多台机器上的多个进程组成的，进程之间采用TCP长连接通信。本章讨论分布式系统中单个服务进程的设计方法，第9章将谈一谈整个系统的设计。我提倡用多线程，并不是说把整个系统放到一个进程里实现，而是指功能划分之后，在实现每一类服务进程时，在必要时可以借助多线程来提高性能。对于整个分布式系统，要做到能 scale out，即享受增加机器带来的好处。\n",
    "\n",
    "使用TCP长连接的好处有两点∶\n",
    "- 一是容易定位分布式系统中的服务之间的依赖关系。只要在机器上运行 `netstat -tpna | grep∶port` 就能立刻列出用到某服务的客户端地址（Foreign 列），然后在客户端的机器上用`netstat` 或`lsof` 命令找出是哪个进程发起的连接。这样在迁移服务的时候能有效地防止出现 outage。TCP 短连接和UDP则不具备这一特性。\n",
    "- 二是通过接收和发送队列的长度也较容易定位网络或程序故障。在正常运行的时候，`netstat` 打印的 Recv-Q和 Send-Q都应该接近`0`，或者在`0`附近摆动。如果 Recv-Q保持不变或持续增加，则通常意味着服务进程的处理速度变慢，可能发生了死锁或阻塞。如果 Send-Q保持不变或持续增加，有可能是对方服务器太忙、来不及处理，也有可能是网络中间某个路由器或交换机故障造成丢包，甚至对方服务器掉线，这些因素都可能表现为数据发送不出去。通过持续监控 Recv-Q和Send-Q就能及早预警性能或可用性故障。\n",
    "\n",
    "以下是服务端线程阻塞造成Recv-Q和客户端 Send-Q激增的例子。\n",
    "\n",
    "<img src=\"./images/3.1.png\" alt=\"image-20251105204357506\" style=\"zoom:50%;\" />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 3.5 * 多线程服务器的适用场合\n",
    "\n",
    "\"服务器开发\"包罗万象，本书所指的\"服务器开发\"的含义请见本章开头，用一句话形容是: 跑在多核机器上的 Linux用户态的没有用户界面的长期运行的网络应用程序，通常是分布式系统的组成部件。\n",
    "> \"长期运行\"的意思不是指程序7×24不重启，而是程序不会因为无事可做而退出，它会等着下一个请求的到来。例如 `wget`不是长期运行的，`httpd`是长期运行的。\n",
    "\n",
    "开发服务端程序的一个基本任务是处理并发连接，现在服务端网络编程处理并发连接主要有两种方式∶\n",
    "- 当\"线程\"很廉价时，一台机器上可以创建远高于CPU数目的\"线程\"。这时一个线程只处理一个TCP连接（甚至半个），通常使用阻塞IO（至少看起来如此）。例如，Python gevent、Go goroutine、Erlang actor。这里的\"线程\"由语言的runtime自行调度，与操作系统线程不是一回事。\n",
    "- 当线程很宝贵时，一台机器上只能创建与CPU数目相当的线程。这时一个线程要处理多个TCP连接上的IO，通常使用非阻塞IO和IO multiplexing。例如，libevent、muduo、Netty。这是原生线程，能被操作系统的任务调度器看见。\n",
    "\n",
    "在处理并发连接的同时，也要充分发挥硬件资源的作用，不能让CPU资源闲置。以上列出的库不是每个都能做到这一点。既然本书讨论的是C++编程，那么只考虑后一种方式，这是在 Linux下使用native语言编写用户态高性能网络程序的最成熟的模式。本节主要讨论的是这些\"线程\"应该属于一个进程（以下模式2），还是分属多个进程（模式3）。\n",
    "\n",
    "与前文相同，本节的\"进程\"指的是 `fork(2)`系统调用的产物。\"线程\"指的是`pthread_create()`的产物，因此是宝贵的那种原生线程。而且我指的 Pthreads 是NPTL的，每个线程由`clone(2)`产生，对应一个内核的task_struct。\n",
    "\n",
    "首先，一个由多台机器组成的分布式系统必然是多进程的（字面意义上），因为进程不能跨OS边界。在这个前提下，我们把目光集中到一台机器，一台拥有至少4个核的普通服务器。\n",
    "如果要在一台多核机器上提供一种服务或执行一个任务，可用的模式有∶（这里的\"模式\"不是 pattern，而是model，不巧它们的中译文是一样的。）\n",
    "\n",
    "1. 运行一个单线程的进程;\n",
    "2. 运行一个多线程的进程;\n",
    "3. 运行多个单线程的进程;\n",
    "4. 运行多个多线程的进程。\n",
    "\n",
    "这些模式之间的比较已经是老生常谈，简单地总结如下。\n",
    "- 模式1是不可伸缩的（scalable ），不能发挥多核机器的计算能力。\n",
    "- 模式3是目前公认的主流模式。它有以下两种子模式∶\n",
    "    - 3a: 简单地把模式1中的进程运行多份 (如果能用多个TCP port 对外提供服务的话。)\n",
    "    - 3b: 主进程 + woker进程，如果必须绑定到一个TCP port，比如 httpd+fastcgi\n",
    "- 模式2是被很多人所鄙视的，认为多线程程序难写，而且与模式3相比并没有什么优势。\n",
    "- 模式4更是千夫所指，它不但没有结合2和3的优点，反而汇聚了二者的缺点。\n",
    "\n",
    "本文主要想讨论的是模式2和模式 3b 的优劣，即∶什么时候一个服务器程序应该是多线程的。\n",
    "- 从功能上讲，没有什么是多线程能做到而单线程做不到的，反之亦然，都是状态机嘛（我很高兴看到反例）。\n",
    "- 从性能上讲，无论是IO bound还是CPU bound 的服务，多线程都没有什么优势。\n",
    "\n",
    "Paul E.McKenney在《[Is Parallel Programming Hard，And，If So，What Can You Do About It?](https://mirrors.edge.kernel.org/pub/linux/kernel/people/paulmck/perfbook/perfbook.html)》第3.5节指出，“As a rough rule of thumb，use the simplest tool that will get the job done.”\n",
    "\n",
    "比方说，使用速率为50MB/s的数据压缩库、在进程创建销毁的开销是800µs、线程创建销毁的开销是50µs的前提下，考虑如何执行压缩任务：\n",
    "- 如果要偶尔压缩1GB的文本文件，预计运行时间是20s，那么起一个进程去做是合理的，因为进程启动和销毁的开销远远小于实际任务的耗时。\n",
    "- 如果要经常压缩500kB的文本数据，预计运行时间是10ms，那么每次都起进程似乎有点浪费了，可以每次单独起一个线程去做。\n",
    "- 如果要频繁压缩10kB的文本数据，预计运行时间是200µs，那么每次起线程似乎也很浪费，不如直接在当前线程搞定。也可以用一个线程池，每次把压缩任务交给线程池，避免阻塞当前线程（特别要避免阻塞IO线程）。\n",
    "\n",
    "由此可见，多线程并不是万灵丹（silver bullet），它有适用的场合。那么究竟什么时候该用多线程?在回答这个问题之前，我先谈谈必须用单线程的场合。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 必须用单线程的场合\n",
    "\n",
    "据我所知，有两种场合必须使用单线程∶\n",
    "\n",
    "+ 程序可能会 `fork(2)`;\n",
    "+ 限制程序的CPU占用率"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 只有单线程程序能 fork(2)\n",
    "\n",
    "根据后面 §4.9 的分析，一个设计为可能调用`fork(2)`的程序必须是单线程的，比如后面§3.5.3中提到的\"看门狗进程\"。多线程程序不是不能调用`fork(2)`，而是这么做会遇到很多麻烦，我想不出做的理由。\n",
    "\n",
    "一个程序`fork(2)`之后一般有两种行为∶\n",
    "- 立刻执行`exec()`，变身为另一个程序。例如 shell 和 inetd; 又比如 lighttpd `fork()`出子进程，然后运行fastcgi程序。或者集群中运行在计算节点上的负责启动 job的守护进程（即我所谓的\"看门狗进程\"）。\n",
    "- 不调用`exec()`，继续运行当前程序。要么通过共享的文件描述符与父进程通信，协同完成任务;要么接过父进程传来的文件描述符，独立完成工作，例如 20世纪 80年代的 Web服务器 NCSA httpd。\n",
    "\n",
    "这些行为中，我认为只有\"看门狗进程\"必须坚持单线程，其他的均可替换为多线程程序（从功能上讲）。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 单线程程序能限制程序的 CPU 占用率\n",
    "\n",
    "这个很容易理解，比如在一个8核的服务器上，一个单线程程序即便发生busy-wait（无论是因为bug，还是因为 overload），占满1个core，其CPU使用率也只有12.5%在这种最坏的情况下，系统还是有87.5%计算资源可供其他服务进程使用。\n",
    "\n",
    "因此对于一些辅助性的程序，如果它必须和主要服务进程运行在同一台机器的话（比如它要监控其他服务进程的状态），那么做成单线程的能避免过分抢夺系统的计算 资源。比方说如果要把生产服务器上的日志文件压缩后备份到 NFS上，那么应该使用普通单线程压缩工具（`gzip/bzip2`）。它们对系统造成的影响较小，在8核服务器上最多占满1个core。如果有人为了\"提高速度\"，开启了多线程压缩或者同时起多个进程来压缩多个日志文件，有可能造成的结果是非关键任务耗尽了 CPU资源，正常客户的请求响应变慢。这是我们不愿意看到的。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 单线程程序的优缺点\n",
    "\n",
    "从编程的角度，单线程程序的优势无须赘言∶简单。程序的结构一般如 §3.2所言，是一个基于IO multiplexing 的event loop。或者如[云风](https://blog.codingnow.com/2006/04/iocp_kqueue_epoll.html)所言，直接用阻塞IO。event loop 的典型代码框架见 §3.2。\n",
    "\n",
    "Event loop有一个明显的缺点，它是非抢占的（non-preemptive）。假设事件 a的优先级高于事件b，处理事件 a需要1ms，处理事件b需要10ms。如果事件b稍早于a发生，那么当事件a到来时，程序已经离开了`poll(2)`调用，并开始处理事件b。事件a要等上10ms 才有机会被处理，总的响应时间为11ms。这等于发生了优先级反转。这个缺点可以用多线程来克服，这也是多线程的主要优势。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 多线程程序有性能优势吗\n",
    "\n",
    "前面我说，无论是IO bound 还是 CPU bound 的服务，多线程都没有什么绝对意义上的性能优势。这句话是说，如果用很少的CPU负载就能让IO跑满，或者用很少的IO流量就能让 CPU 跑满，那么多线程没啥用处。\n",
    "\n",
    "举例来说∶\n",
    "- 对于静态Web 服务器，或者FTP 服务器，CPU的负载较轻，主要瓶颈在磁盘IO和网络IO方面。这时候往往一个单线程的程序（模式1）就能撑满 IO。用多线程并不能提高吞吐量，因为IO硬件容量已经饱和了。同理，这时增加CPU数目也不能提高吞吐量。\n",
    "- CPU跑满的情况比较少见，这里我只好虚构一个例子。假设有一个服务，它的输入是n个整数，问能否从中选出m个整数，使其和为0（这里n < 100，m > 0）。这是著名的 subset sum 问题，是NP-Complete 的。对于这样一个\"服务\"，哪怕很小的n值也会让 CPU算死。比如n=30，一次的输入不过200字节（32-bit整数），CPU的运算时间却能长达几分钟。对于这种应用，模式3a是最适合的，能发挥多核的优势，程序也简单。\n",
    "\n",
    "也就是说，无论任何一方早早地先到达瓶颈，多线程程序都没啥优势。\n",
    "\n",
    "说到这里，可能已经有读者不耐烦了∶你讲了这么多，都在说单线程的好处，那么多线程究竟有什么用?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## * 适用多线程程序的场景\n",
    "\n",
    "我认为多线程的适用场景是∶提高响应速度、让IO和\"计算\"相互重叠，降低latency。虽然多线程不能提高绝对性能，但能提高平均响应性能。\n",
    "\n",
    "一个程序要做成多线程的，大致要满足∶\n",
    "- 有多个CPU可用。单核机器上多线程没有性能优势（但或许能简化并发业务逻辑的实现）。\n",
    "- 线程间有共享数据，即内存中的全局状态。如果没有共享数据，用模型3b 就行。虽然我们应该把线程间的共享数据降到最低，但不代表没有。\n",
    "- 共享的数据是可以修改的，而不是静态的常量表。如果数据不能修改，那么可以在进程间用shared memory，模式3就能胜任。\n",
    "- 提供非均质的服务。即，事件的响应有优先级差异、我们可以用专门的线程来处理优先级高的事件。防止优先级反转。\n",
    "- latency和 throughput同样重要，不是逻辑简单的IO bound或 CPU bound程序。换言之，程序要有相当的计算量。\n",
    "- 利用异步操作。比如 logging。无论往磁盘写log file，还是往log server发送消息都不应该阻塞critical path。\n",
    "- 能 scale up。一个好的多线程程序应该能享受增加CPU数目带来的好处，目前主流是8核，很快就会用到16核的机器了。\n",
    "- 具有可预测的性能。随着负载增加，性能缓慢下降，超过某个临界点之后会急速下降。线程数目一般不随负载变化。\n",
    "- 多线程能有效地划分责任与功能，让每个线程的逻辑比较简单，任务单一，便于编码。而不是把所有逻辑都塞到一个event loop 里，不同类别的事件之间相互影响。\n",
    "\n",
    "这些条件比较抽象，这里举两个具体的（虽然是虚构的）例子。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "假设要管理一个Linux 服务器机群，这个机群里有8个计算节点，1个控制节点。机器的配置都是一样的，双路四核CPU，千兆网互联。\n",
    "\n",
    "现在需要编写一个简单的机群管理软件（参考LLNL的 SLURM），这个软件由3个程序组成∶\n",
    "1. 运行在控制节点上的 master，这个程序监视并控制整个机群的状态。\n",
    "2. 运行在每个计算节点上的 slave，负责启动和终止 job，并监控本机的资源。\n",
    "3. 供最终用户使用的 client命令行工具，用于提交job。\n",
    "\n",
    "根据前面的分析，slave 是个\"看门狗进程\"，它会启动别的job 进程，因此必须是个单线程程序。另外它不应该占用太多的CPU资源，这也适合单线程模型。\n",
    "\n",
    "master应该是个模式2的多线程程序∶\n",
    "- 它独占一台8核的机器，如果用模型1，等于浪费了87.5%的CPU资源。\n",
    "- 整个机群的状态应该能完全放在内存中，这些状态是共享且可变的。如果用模式3，那么进程之间的状态同步会成大问题。而如果大量使用共享内存，则等于是掩耳盗铃，是披着多进程外衣的多线程程序。因为一个进程一旦在临界区内阻塞或 crash，其他进程会全部死锁。\n",
    "- master的主要性能指标不是throughput，而是latency，即尽快地响应各种事件。它几乎不会出现把IO或CPU跑满的情况。\n",
    "- master监控的事件有优先级区别，一个程序正常运行结束和异常崩溃的处理优先级不同，计算节点的磁盘满了和机箱温度过高这两种报警条件的优先级也不同。如果用单线程，则可能会出现优先级反转。\n",
    "- 假设master 和每个slave之间用一个TCP连接，那么 master采用2个或4个IO线程来处理8个 TCP connections 能有效地降低延迟。\n",
    "- master要异步地往本地硬盘写log，这要求 logging library有自己的IO线程。\n",
    "- master 有可能要读写数据库，那么数据库连接这个第三方library 可能有自己的线程，并回调 master的代码。\n",
    "- master 要服务于多个clients，用多线程也能降低客户响应时间。也就是说它可以再用2个IO线程专门处理和 clients 的通信。\n",
    "- master还可以提供一个monitor接口，用来广播推送（pushing）机群的状态，这样用户不用主动轮询（polling）。这个功能如果用单独的线程来做，会比较容易实现，不会搞乱其他主要功能。\n",
    "- master一共开了10个线程∶\n",
    "    - 4个用于和 slaves通信的IO线程。\n",
    "    - 1个logging线程。\n",
    "    - 1个数据库IO线程。\n",
    "    - 2个和 clients 通信的IO线程。\n",
    "    - 1个主线程，用于做些背景工作，比如 job 调度。\n",
    "    - 1个pushing 线程，用于主动广播机群的状态。\n",
    "- 虽然线程数目略多于core数目，但是这些线程很多时候都是空闲的，可以依赖OS的进程调度来保证可控的延迟。\n",
    "\n",
    "综上所述，master 用多线程方式编写是自然且高效的。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "再举一个TCP聊天服务器的例子，这里的\"聊天\"不完全指人与人聊天，也可能是机器与机器\"聊天\"。这种服务的特点是并发连接之间有数据交换，从一个连接收到的数据要转发给其他多个连接。因此我们不能按模式3的做法。把多个连接分到多个进程中分别处理（这会带来复杂的进程间通信），而只能用模式1或者模式2。如果纯粹只有数据交换，那么我想模式1也能工作得很好，因为现在的CPU 足够快，单线程应付几百个连接不在话下。\n",
    "\n",
    "如果功能进一步复杂化，加上关键字过滤、黑名单、防灌水等等功能，甚至要给聊天内容自动加上相关连接，每一项功能都会占用CPU资源。这时就要考虑模式2了，因为单个CPU 的处理能力显得捉襟见肘，顺序处理导致消息转发的延迟增加。这时我们考虑把空闲的多个CPU 利用起来，自然的做法是把连接分散到多个线程上，例如按 round-robin 的方式把1000个客户连接分配到4个IO线程上。这样充分利用多核加速。具体的例子见§6.6的方案9，以及 p.260-多线程的高效广播的实现。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 线程的分类\n",
    "\n",
    "据我的经验，一个多线程服务程序中的线程大致可分为3类;\n",
    "- IO线程，这类线程的主循环是IO multiplexing，阻塞地等在`select/poll/epoll_wait`系统调用上。这类线程也处理定时事件。当然它的功能不止IO，有些简单计算也可以放入其中，比如消息的编码或解码。\n",
    "- 计算线程，这类线程的主循环是blocking queue，阻塞地等在condition variable上。这类线程一般位于thread pool中。这种线程通常不涉及 IO，一般要避免任何阻塞操作。\n",
    "- 第三方库所用的线程，比如logging，又比如 database connection。\n",
    "\n",
    "服务器程序一般不会频繁地启动和终止线程。甚至，在我写过的程序里，create thread 只在程序启动的时候调用，在服务运行期间是不调用的。\n",
    "\n",
    "在多核时代，要想充分发挥CPU性能，多线程编程是不可避免的，\"鸵鸟算法\"不是办法。在学会多线程编程之前，我也一直认为单线程服务程序才是王道。在接触多线程编程之后，经过一段时间的训练和适应，我已能比较自如地编写正确且足够高效的多线程程序。学习多线程编程还有一个好处，即训练异步思维，提高分析并发事件的能力。这对设计分布式系统帮助巨大，因为运行在多台机器上的服务进程本质上是异步的。熟悉多线程编程的话，很容易就能发现分布式系统在消息和事件处理方面的 race condition。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 3.6 \"多线程服务器的适用场合\"例释与答疑\n",
    "\n",
    "[《多线程服务器的适用场合》](https://blog.csdn.net/Solstice/article/details/5334243)一文在博客登出之后，有热心读者提出质疑，我自己也觉得原文没有把道理说通、说透，下面用一些实例来解答读者的疑问。\n",
    "\n",
    "为方便阅读，本节以问答体呈现。以下\"连接、端口\"均指TCP 协议。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 1. Linux能同时启动多少个线程?\n",
    "\n",
    "对于32-bit Linux，一个进程的地址空间是4GiB，其中用户态能访问3GiB左右，而一个线程的默认栈（stack）大小是10MB，心算可知，一个进程大约最多能同时启动300个线程。如果不改线程的调用栈大小的话，300左右是上限，因为程序的其他部分（数据段、代码段、堆、动态库等等）同样要占用内存（地址空间）。\n",
    "\n",
    "对于64-bit 系统，线程数目可大大增加，具体数字我没有测试过，因为我在实际项目中一台机器上最多只用到过几十个用户线程，其中大部分还是空闲的。\n",
    "\n",
    "下面的第2问关于线程数目的讨论以32-bit Linux 为例。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2. 多线程能提高并发度吗?\n",
    "\n",
    "如果指的是\"并发连接数\"，则不能。\n",
    "\n",
    "由问题1可知，假如单纯采用`thread per connection`的模型，那么并发连接数最多 300，这远远低于基于事件的单线程程序所能轻松达到的并发连接数（几千乃至上万，甚至几万）。所谓\"基于事件\"，指的是用`IO multiplexing event loop` 的编程模型，又称 Reactor模式，在前文中已有介绍。\n",
    "\n",
    "那么采用前文中推荐的 one loop per thread 呢?至少不逊于单线程程序。实际上单个event loop 处理1万个并发长连接并不罕见，一个multi-loop 的多线程程序应该能轻松支持5万并发链接。\n",
    "\n",
    "小结∶thread per connection不适合高并发场合，其scalability 不佳。one loopper thread 的并发度足够大，且与CPU数目成正比。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## * 3. 多线程能提高吞吐量吗?\n",
    "\n",
    "对于计算密集型服务，不能。\n",
    "\n",
    "假设有一个耗时的计算服务，用单线程算需要0.8s。在一台8核的机器上，我们可以启动8个线程一起对外服务（如果内存够用，启动8个进程也一样）。这样完成单个计算仍然要 0.8s，但是由于这些进程的计算可以同时进行，理想情况下吞吐量可以从单线程的1.25qps （query per second）上升到10qps。（实际情况可能要打个八折——如果不是打对折的话。）\n",
    "\n",
    "假如改用并行算法，用8个核一起算，理论上如果完全并行，加速比高达8，那么计算时间是0.1s，吞吐量还是10gps，但是首次请求的响应时间却降低了很多。实际上根据 Amdahl's law，即便算法的并行度高达 95%, 8核的加速比也只有6，计算时间为0.133s，这样会造成吞吐量下降为7.5qps。不过以此为代价，换得响应时间的提升，在有些应用场合也是值得的。\n",
    "\n",
    "再举个例子，如果要在一台8核机器上压缩100个1GB的文本文件，每个core的处理能力为200MB/s。那么\"每次起8个进程，每个进程压缩1个文件\"与\"依次压缩每个文件，每个文件用8个线程并行压缩\"这两种方式的总耗时相当，因为CPU都是满载的。但是第2种方式能较快地拿到第一个压缩完的文件，也就是首次响应的延时更小。\n",
    "\n",
    "这也回答了问题4。\n",
    "\n",
    "如果用 thread per request 的模型，每个客户请求用一个线程去处理，那么当并发请求数大于某个临界值T'时，吞吐量反而会下降，因为线程多了以后上下文切换的开销也随之增加（分析与数据请见[《A Design Framework for Highly ConcurrentSystems》](http://www.cs.berkeley.edu/~culler/papers/events.pdf)）。thread per request 是最简单的使用线程的方式，编程最容易，简单地把多线程程序当成一堆串行程序，用同步的方式顺序编程，比如在 Java Servlet 2.x中，一次页面请求由一个函数`HttpServlet.service(HttpServletRequest req, HttpServletResponse resp)`同步地完成。\n",
    "\n",
    "为了在并发请求数很高时也能保持稳定的吞吐量，我们可以用线程池，线程池的大小应该满足\"阻抗匹配原则\"，见问题7。\n",
    "\n",
    "线程池也不是万能的，如果响应一次请求需要做比较多的计算（比如计算的时间占整个response time 的1/5强），那么用线程池是合理的，能简化编程。如果在一次请求响应中，主要时间是在等待IO，那么为了进一步提高吞吐量，往往要用其他编程模型，比如 Proactor. 见问题 8。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## * 4. 多线程能降低响应时间吗?\n",
    "\n",
    "如果设计合理，充分利用多核资源的话，可以。在突发（burst）请求时效果尤为明显。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 例1∶多线程处理输入\n",
    "\n",
    "以 memcached 服务端为例。memcached一次请求响应大概可以分为3步∶\n",
    "- 读取并解析客户端输入\n",
    "- 操作hashtable\n",
    "- 返回客户端\n",
    "\n",
    "在单线程模式下，这3步是串行执行的。在启用多线程模式时，它会启用多个输人线程（默认是4个），并在建立连接时按 round-robin 法把新连接分派给其中一个输入线程，这正好是我说的 one loop per thread模型。这样一来，第1步的操作就能多线程并行，在多核机器上提高多用户的响应速度。第2步用了全局锁，还是单线程的，这可算是一个值得继续改进的地方。\n",
    "\n",
    "比如，有两个用户同时发出了请求，这两个用户的连接正好分配在两个IO线程上，那么两个请求的第1步操作可以在两个线程上并行执行，然后汇总到第2步串行执行，这样总的响应时间比完全串行执行要短一些（在\"读取并解析\"所占的比重较大的时候，效果更为明显）。\n",
    "\n",
    "请继续看下面这个例子。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 例2∶多线程分担负载\n",
    "\n",
    "假设我们要做一个[求解 Sudoku 的服务](https://blog.csdn.net/Solstice/article/details/2096209)，这个服务程序在9981端口接受请求，输入为一行81个数字（待填数字用0表示），输出为填好之后的81个数字（1~9），如果无解，输出`\"NO\\r\\n\"`。\n",
    "\n",
    "由于输入格式很简单，用单个线程做IO 就行了。先假设每次求解的计算用时为10ms，用前面的方法计算，单线程程序能达到的吞吐量上限为100qps;在8核机器上，如果用线程池来做计算，能达到的吞吐量上限为800qps。下面我们看看多线程如何降低响应时间。\n",
    "\n",
    "假设1个用户在极短的时间内发出了10个请求，如果用单线程\"来一个处理一个\"的模型，这些reqs 会排在队列里依次处理（这个队列是操作系统的 TCP缓冲区，不是程序里自已的任务队列）。在不考虑网络延迟的情况下，第1个请求的响应时间是10ms;第2个请求要等第1个算完了才能获得CPU资源，它等了10ms，算了10ms，响应时间是20ms;依此类推，第10个请求的响应时间为100ms;这10个请求的平均响应时间为 55ms。\n",
    "\n",
    "如果 Sudoku 服务在每个请求到达时开始计时，会发现每个请求都是 10ms 响应时间;而从用户的观点来看，10 个请求的平均响应时间为 55ms，请读者想想为什么会有这个差异。\n",
    "\n",
    "下面改用多线程∶1个IO线程，8个计算线程（线程池）。二者之间用BlockingQueue 沟通。同样是10个并发请求，第1个请求被分配到计算线程1，第2个请求被分配到计算线程2，依此类推，直到第8个请求被第8个计算线程承担。第9和第 10号请求会等在BlockingQueue 里，直到有计算线程回到空闲状态其才能被处理。（请注意，这里的分配实际上由操作系统来做，操作系统会从处于waiting 状态的线程里挑一个，不一定是round-robin 的。）这样一来，前8个请求的响应时间差不多都是 10ms，后2个请求属于第二批，其响应时间大约会是 20ms，总的平均响应时间是12ms。可以看出这比单线程快了不少。\n",
    "\n",
    "由于每道 Sudoku题目的难度不一，对于简单的题目，可能1ms 就能算出来，复杂的题目最多用10ms。那么线程池方案的优势就更明显，它能有效地降低\"简单任务被复杂任务压住\"的出现概率。\n",
    "\n",
    "以上举的都是计算密集的例子，即线程在响应一次请求时不会等待 IO。下面谈谈更复杂的情况。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## * 5. 多线程程序如何让IO和\"计算\"相互重叠，降低latency?\n",
    "\n",
    "基本思路是，把IO操作（通常是写操作）通过BlockingQueue 交给别的线程去做，自己不必等待。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 例1∶日志（logging）\n",
    "\n",
    "在多线程服务器程序中，日志（logging）至关重要，本例仅考虑写 log file的情况，不考虑log server。\n",
    "\n",
    "在一次请求响应中，可能要写多条日志消息，而如果用同步的方式写文件（fprintf或 fwrite），多半会降低性能，因为∶\n",
    "- 文件操作一般比较慢，服务线程会等在IO上，让CPU闲置，增加响应时间。\n",
    "- 就算有buffer，还是不灵。多个线程一起写，为了不至于把buffer写错乱，往往要加锁。这会让服务线程互相等待，降低并发度。（同时用多个log 文件不是办法，除非你有多个磁盘，且保证 log files 分散在不同的磁盘上，否则还是要受到磁盘IO瓶颈的制约。）\n",
    "\n",
    "解决办法是单独用一个logging 线程，负责写磁盘文件，通过一个或多个 `BlockingQueue` 对外提供接口。别的线程要写日志的时候，先把消息（字符串）准备好，然后往 queue 里一塞就行，基本不用等待。这样服务线程的计算就和logging 线程的磁盘IO 相互重叠，降低了服务线程的响应时间。\n",
    "\n",
    "尽管logging 很重要，但它不是程序的主要逻辑，因此对程序的结构影响越小越好，最好能简单到如同一条 `printf`语句，且不用担心其他性能开销。而一个好的多线程异步logging库能帮我们做到这一点，见第5章。（Apache 的log4cxx 和log4j都支持AsyncAppender 这种异步logging 方式。）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 例2∶memcached客户端 \n",
    "\n",
    "假设我们用memcached来保存用户最后发帖的时间，那么每次响应用户发帖的请求时，程序里要去设置一下memcached 里的值。这一步如果用同步IO，会增加延迟。\n",
    "\n",
    "对于\"设置一个值\"这样的 write-only idempotent操作，我们其实不用等memcached 返回操作结果，这里也不用在乎 set 操作失败，那么可以借助多线程来降低响应延迟。比方说我们可以写一个多线程版的 memcached 的客户端，对于set操作，调用方只要把 key 和 value 准备好，调用一下 `asyncSet()`函数，把数据往BlockingQueue上一放就能立即返回，延迟很小。剩下的事就留给 memcached客户端的线程去操心，而服务线程不受阻碍。\n",
    "\n",
    "其实所有的网络写操作都可以这么异步地做，不过这也有一个缺点，那就是每次`asyncwrite()`都要在线程间传递数据。其实如果 TCP缓冲区是空的，我们就可以在本线程写完，不用劳烦专门的IO线程。Netty 就使用了这个办法来进一步降低延迟。\n",
    "\n",
    "以上都仅讨论了\"打一枪就跑\"的情况，如果是一问一答，比如从 memcached取一个值，那么\"重叠IO\"并不能降低响应时间，因为你无论如何要等memcached的回复。这时我们可以用别的方式来提高并发度，见问题 8。（虽然不能降低响应时间，但也不要浪费线程在空等上。）\n",
    "\n",
    "以上的例子也说明，BlockingQueue 是构建多线程程序的利器。另见§12.8.3。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 6. 为什么第三方库往往要用自己的线程?\n",
    "\n",
    "event loop 模型没有标准实现。如果自己写代码，尽可以按所用Reactor 的推荐方式来编程。但是第三方库不一定能很好地适应并融入这个event loop framework，有时需要用线程来做一些串并转换。比方说检测串口上的数据到达可以用文件描述符的可读事件，因此可以方便地融入 event loop。但是检测串口上的某些控制信号（例如 DCD）只能用轮询(`ioctl(fd，TIoCMGET，&flags)`)或阻塞等待(`ioctl（fd，TIOCMIWAIT，TIOCM_CAR)`);要想融入 event loop，需要单独起一个线程来查询串口信号翻转，再转换为文件描述符的读写事件（可以通过`pipe(2)`）。\n",
    "\n",
    "对于Java，这个问题还好办一些，因为 thread pool在 Java 里有标准实现，叫ExecutorService。如果第三方库支持线程池，那么它可以和主程序共享一个ExecutorService，而不是自己创建一堆线程。（比如在初始化时传入主程序的 obj。）对于 C++，情况麻烦得多，Reactor 和 thread pool都没有标准库。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 例1∶libmemcached 只支持同步操作\n",
    "\n",
    "libmemcached 支持所谓的\"非阻塞操作\"，但没有暴露一个能被`select/poll/epoll`的 file describer，它的 `memcached_fetch` 始终会阻塞。它号称`memcached_set` 可以是非阻塞的，实际意思是不必等待结果返回，但实际上这个函数会阻塞地调用`write(2)`，仍可能阻塞在网络 IO上。\n",
    "\n",
    "如果在我们的 Reactor event handler 里调用了libmemcached 的函数，那么latency 就堪忧了。如果想继续用 libmemcached，我们可以为它做一次线程封装，按问题5例2的办法，同额外的线程专门做 memcached 的IO，而程序主体还是Reactor。甚至可以把 memcached 的\"数据就绪\"作为一个event，注入我们的 event loop 中，以进一步提高并发度。（例子留待问题 8讲。）\n",
    "\n",
    "万幸的是，memcached 的协议非常简单，大不了可以自己写一个基于Reactor的客户端，但是数据库客户端就没那么幸运了。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 例2∶MySQL的官方CAPI不支持异步操作\n",
    "\n",
    "MySQL的官方客户端只支持同步操作，对于`UPDATE/INSERT/DELETE` 之类只要行为不管结果的操作（如果代码需要得知其执行结果，则另当别论），我们可以用一个单独的线程来做，以降低服务线程的延迟。可仿照前面 `memcached_set` 的例子，不再赘言。麻烦的是 `SELECT`，如果要把它也异步化，就得动用更复杂的模式了，见问题8。\n",
    ">  非官方的 libdrizzle 似乎支持异步操作，见 https://github.com/openresty/drizzle-nginx-module。\n",
    "\n",
    "相比之下，PostgreSQL的C客户端 libpq 的设计要好得多，我们可以用`PQsendQuery()`来发起一次查询，然后用标准的 `select/poll/epoll`来等待 PQsocket。如果有数据可读，那么用`PQconsumeInput`处理之，并用`PQisBusy`判断查询结果是否已就绪。最后用`PQgetResult`来获取结果。借助这套异步API，我们可以很容易地为libpq写一套 wrapper，使之融入程序所用的 event loop 模型中。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 7. 什么是线程池大小的阻抗匹配原则?\n",
    "\n",
    "我在前文中提到“阻抗匹配原则”，这里大致讲一讲。\n",
    "\n",
    "如果池中线程在执行任务时，密集计算所占的时间比重为 $P$（$0 < P \\le 1$），而系统一共有 $C$ 个 CPU，为了让这 $C$ 个 CPU 跑满而又不过载，线程池大小的经验公式是 $T = \\frac{C}{P}.$\n",
    "\n",
    "$T$ 只是一个 hint，考虑到 $P$ 值的估计不是很准确，$T$ 的最佳值可以上下浮动 $50\\%$。这个经验公式的原理很简单：$T$ 个线程，每个线程占用 $P$ 的 CPU 时间，如果刚好占满 $C$ 个 CPU，那么必有 $T \\times P = C.$\n",
    "\n",
    "下面验证一下边界条件的正确性。\n",
    "\n",
    "- 假设 $C = 8$，$P = 1.0$，线程池的任务完全是密集计算，那么 $T = 8$。只要 8 个活动线程就能让 8 个 CPU 饱和，再多也没用，因为 CPU 资源已经耗光了。\n",
    "- 假设 $C = 8$，$P = 0.5$，线程池的任务有一半是计算，有一半等在 IO 上。那么 $T = 16$。考虑操作系统能灵活、合理地调度 sleeping/writing/running 线程，那么大概 16 个“50% 忙的线程”能让 8 个 CPU 忙个不停。启动更多的线程并不能提高吞吐量，反而因为增加上下文切换的开销而降低性能。\n",
    "\n",
    "如果 $P < 0.2$，这个公式就不适用了，$T$ 可以取一个固定值，比如 $5 \\times C$。另外，公式里的 $C$ 不一定是 CPU 总数，可以是“分配给这项任务的 CPU 数目”，比如在 8 核机器上分出 4 个核来做一项任务，那么 $C = 4$。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> 线程池的阻抗匹配原则就是让线程池大小 $T \\approx C / P$，使得 CPU 核心数 $C$ 与每个线程实际占用的 CPU 比例 $P$ 相匹配，从而既跑满 CPU 又不过载。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 8. 除了你推荐的Reactor+ thread poll，还有别的 non-trivial 多线程编程模型吗?\n",
    "\n",
    "有，Proactor。如果一次请求响应中要和别的进程打多次交道，那么 Proactor 模型往往能做到更高的并发度。当然，代价是代码变得支离破碎，难以理解。\n",
    "\n",
    "这里举 HTTP proxy为例，一次 HTTP proxy 的请求如果没有命中本地 cache，那么它多半会∶\n",
    "- 解析域名（不要小看这一步，对于一个陌生的域名，解析可能要花几秒的时间）\n",
    "- 建立连接\n",
    "- 发送 HTTP请求\n",
    "- 等待对方回应\n",
    "- 把结果返回给客户\n",
    "\n",
    "这5步中跟2个server发生了3次 round-trip，每次都可能花几百毫秒∶\n",
    "- 向 DNS问域名，等待回复\n",
    "- 向对方的 HTTP 服务器发起连接，等待TCP三路握手完成\n",
    "- 向对方发送 HTTP request，等待对方 response\n",
    "\n",
    "而实际上 HTTP proxy 本身的运算量不大，如果用线程池，池中线程的数目会很庞大，不利于操作系统的管理调度。\n",
    "\n",
    "这时我们有两个解决思路∶\n",
    "- 把\"域名已解析\"、\"连接已建立\"、\"对方已完成响应\"做成event，继续按照Reactor 的方式来编程。这样一来，每次客户请求就不能用一个函数从头到尾执行完成，而要分成多个阶段，并且要管理好请求的状态（\"目前到了第几步?\"）。\n",
    "- 用回调函数，让系统来把任务串起来。比如收到用户请求，如果没有命中本地缓存，那么需要执行∶\n",
    "    - 立刻发起异步的DNS解析`startDNSResolve()`，告诉系统在解析完之后调用`DNSResolved()`函数;\n",
    "    - 在`DNSResolved()`中，发起 TCP连接请求，告诉系统在连接建立之后调用`connectionEstablished()`;\n",
    "    - 在`connectionEstablished()`中发送HTTP request，告诉系统在收到响应之后调用`httpResponsed()`;\n",
    "    - 最后，在`httpResponsed()`里把结果返回给客户。\n",
    "\n",
    ".NET大量采用的 BeginInvoke/EndInvoke 操作也是这个编程模式。当然，对于不熟悉这种编程方式的人，代码会显得很难看。有关 Proactor 模式的例子可参看 Boost.Asio的文档，这里不再多说。\n",
    "\n",
    "Proactor模式依赖操作系统或库来高效地调度这些子任务，每个子任务都不会阻塞，因此能用比较少的线程达到很高的 IO并发度。\n",
    "\n",
    "Proactor 能提高吞吐，但不能降低延迟，所以我没有深入研究。另外，在没有语言直接支持的情况下，Proactor 模式让代码非常破碎，在C++中使用Proactor是很痛苦的。因此最好在\"线程\"很廉价的语言中使用这种方式，这时runtime往往会屏蔽细节，程序用单线程阻塞IO的方式来处理 TCP连接。\n",
    "> 有的语言能通过库扩展，例如 https://github.com/JeffreyZhao/jscex。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 9. 模式2和模式3a该如何取舍?\n",
    "\n",
    "§3.5中提到，模式2是一个多线程的进程，模式 3a是多个相同的单线程进程。\n",
    "\n",
    "我认为，在其他条件相同的情况下，可以根据工作集（work set）的大小来取舍。工作集是指服务程序响应一次请求所访问的内存大小。\n",
    "\n",
    "如果工作集较大，那么就用多线程，避免 CPU cache换入换出，影响性能; 否则，就用单线程多进程，享受单线程编程的便利。\n",
    "\n",
    "举例来说\n",
    "- 如果程序有一个较大的本地 cache，用于缓存一些基础参考数据（in-memory look-up table），几乎每次请求都会访问 cache，那么多线程更适合一些，因为可以避免每个进程都自己保留一份 cache，增加内存使用。\n",
    "- memcached 这个内存消耗大户用多线程服务端就比在同一台机器上运行多个memcached instance 要好。（但是如果你在 16GiB内存的机器上运行32-bitmemcached，那么此时多instance是必需的。）\n",
    "- 求解 Sudoku用不了多大内存。如果单线程编程更方便的话，可以用单线程多进程来做。再在前面加一个单线程的load balancer，仿lighttpd+ fastcgi的成例。\n",
    "\n",
    "线程不能减少工作量，即不能减少 CPU时间。如果解决一个问题需要执行一亿条指令（这个数字不大，不要被吓到），那么用多线程只会让这个数字增加。但是通过合理调配这一亿条指令在多个核上的执行情况，我们能让工期提早结束。这听上去像统筹方法，其实也确实是统筹方法。"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "C++17",
   "language": "C++17",
   "name": "xcpp17"
  },
  "language_info": {
   "name": "C++17"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
